{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-maUy0fHNEsy"
      },
      "source": [
        "## Search Exercise 4\n",
        "# The Knight's Tour\n",
        "\n",
        "The Knight’s Tour puzzle is the problem of finding a sequence of moves of a single knight on a chess board, such that the knight visits every square on the board exactly once. The knight may begin on any square and must move according to the normal rules for moving a knight in Chess.\n",
        "Normally, a standard 8x8 board is used, but essentially the same problem can be specified for any board dimensions. Here is an animation of a Knight's Tour on a 5x5 board (from Wikimedia Commons):\n",
        "\n",
        "<center>\n",
        "<img src=\"https://upload.wikimedia.org/wikipedia/commons/c/ca/Knights-Tour-Animation.gif\">\n",
        "</center>\n",
        "    \n",
        "\n",
        "You can find a very good description of the Knight's Tour problme in in its [Wikipedia entry](https://en.wikipedia.org/wiki/Knight%27s_tour).\n",
        "A more mathematical presentation can  be  found  at\n",
        "[mathworld.wolfram.com](https://mathworld.wolfram.com/KnightGraph.html)\n",
        "For rules of movement in chess see http://en.wikipedia.org/wiki/Rules_of_chess#Basic_moves.\n",
        "\n",
        "\n",
        "\n",
        "A solution to the problem is a sequence of positions where each position can be reached by a knight's move from the previous position. To discover a solution we can generate different sequences until we find one that satisfies all the requirements of the problem. Because there are lots of different moves that we could try, the order that we consider the possibilities can make a big difference to how quickly a solution is found. \n",
        "\n",
        "Although we are using the Knight's Tour as an example, the same kind of thinking can be applied to a wide variety of puzzles and problems in computer science. We know the rules that a solution must follow, the conditions that must be satisfied, and there are many candidates to search through. We need a systematic and efficient way of approaching this search. \n",
        "\n",
        "The search is commonly thought of as a tree. Each node represents a _state_ that the puzzle can be in. \n",
        "\n",
        "#### Representing a state\n",
        "In the Knight's Tour, a state is the current position of the Knight and a record of which squares have been visited so far. We can use a tuple to hold this information. In addition, we will record the number of moves made so far. So a state is the tuple\n",
        "```\n",
        "(move_number, (current_x_position, current_y_position),  full_board)\n",
        "```\n",
        "The board can be represented using a matrix, i.e. a list of lists.\n",
        "If we have a board which measures 4 squares horizontally (x) and 3 squares vertically (y) this can be represented by\n",
        "```\n",
        "[[0, 0, 0, 0],\n",
        " [0, 0, 0, 0],\n",
        " [0, 0, 0, 0]]\n",
        "```\n",
        "A position on the board is then naturally represented by its x and y co-ordinate.\n",
        "Notice that the usual way to write x and y co-ordinates is with the x value first, but that with list indexing we need to use the y value first.\n",
        "For example, if the board is stored as a list of lists in a variable called `full_board` then position (1,2) would be accessed by `full_board[2][1]`.\n",
        "\n",
        "When a position is visited we can change the 0 to a 1 to indicate this.\n",
        "In order to show how the Knight has moved so far we will actually change the relevant value to show the number of the move which visited each square.\n",
        "So if the Knight began at position (0,1) then moved to (2,0) and is now at (1,2) we would represent this with the board\n",
        "```\n",
        "[[0, 0, 2, 0],\n",
        " [1, 0, 0, 0],\n",
        " [0, 3, 0, 0]]\n",
        "```\n",
        "and the whole state would be given by \n",
        "```\n",
        "(3, (1,2), [[0, 0, 2, 0], [1, 0, 0, 0], [0, 3, 0, 0]])\n",
        "```\n",
        "\n",
        "#### Possible moves\n",
        "From the current position of (1,2) the Knight can either move to (0,0) or (3,1). It would be able to move to (2,0) except that this square has already been visited. Generally, a Knight can make up to eight different moves from its current position: either the x value is changed by 2 and the y value by 1, or the x value is changed by 1 and the y value by 2. \n",
        "The possible moves can be represented by the following eight tuples.\n",
        "```\n",
        "(1,2),   (2,1),  \n",
        "(-1,2),  (2,-1), \n",
        "(1,-2),  (-2,1), \n",
        "(-1,-2), (-2,-1)\n",
        "```\n",
        "From the current position of (1,2) the moves (-1,-2) and (2,-1) take us to (0,0) and (3,1) respectively. The move (1,-2) would take us to (2,0), and all other moves result in co-ordinates outside of the board so are forbidden in this case. To check whether a move is viable we need to check whether either of the x or y co-ordinates that would result from applying it are negative or greater than the board size, and we need to check if the position has been previously visited. \n",
        "\n",
        "From (1,2) we attempt to apply the eight moves and discover that two of them are possible. Now we can decide which to try first.\n",
        "Suppose we apply the move (-1,-2) first. Now the state is \n",
        "```\n",
        "(4, (0,0), [[4, 0, 2, 0], [1, 0, 0, 0], [0, 3, 0, 0]])\n",
        "\n",
        "```\n",
        "\n",
        "#### Ordering the search\n",
        "At this point we could decide to continue from the current state. For the next move we only have one option, which takes us to position (2,1), a couple of moves later there will be another choice to make. Eventually we will find that this attempt ends in failure. We can return to an earlier state and make different choices.\n",
        "Alternatively, we could pause this attempt and generate the state which results from applying (2,-1) as the fourth move. Then we could generate the possible fifth moves from both states before moving on to the possible sixth moves and so on. \n",
        "These two approaches roughly describe a *depth first search* and a *breadth first search*.\n",
        "\n",
        "The possible states are imagined as forming a tree. \n",
        "The root node represents the initial state, nothing has happened yet.\n",
        "The children of this node represent the possible states after one move.\n",
        "In general, the child of a node represents a state which can be reached from this node in one further move. \n",
        "Conceptually, we search through this tree of states until we find a \"winning\" state, one which satisfies our criteria for success. \n",
        "In the case of the Kinight's Tour puzzle, that means a state in which there are no remaining zeros in the lists representing the board.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oQzcCT12NEs-"
      },
      "source": [
        "## Solving Knight's Tour with `bbSearch`\n",
        "\n",
        "We will now see how the Kight's Tour problem can be solved using Brandon's `bbSearch` module, that implemets a general purpose `SearchProblem` class and `search` function.\n",
        "\n",
        "First install the module:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Blkpj5mBNEs_"
      },
      "outputs": [],
      "source": [
        "!mkdir -p bbmodcache\n",
        "!curl http://bb-ai.net.s3.amazonaws.com/bb-python-modules/bbSearch.py > bbmodcache/bbSearch.py\n",
        "from bbmodcache.bbSearch import SearchProblem, search"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eo8nRYO8NEtA"
      },
      "source": [
        "### Defining the `KnightsTour` extension of `SearchProblem`\n",
        "\n",
        "Encoding of the Knight's Tour puzzle as a search problem is relatively straightforward.\n",
        "Read the following code, paying particular attention to the `possible_actions` method.\n",
        "This uses the list of possible `moves` to work out possible end locations after moving the Knight.\n",
        "The possibile moves are restricted to those where the knight stays on the board and moves to a square that it has not been occupied before. The `state` keeps track of which squares have been previously occupied since they will have non-zero values (corresponding to the move number when they were visited).\n",
        "\n",
        "Note that the initialisation finction `__init__` allows us to specify different board sizes in terms of the number of squares in each of the `X` and `Y` dimensions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "z7GmXoTnNEtB"
      },
      "outputs": [],
      "source": [
        "from copy import deepcopy \n",
        "\n",
        "class KnightsTour( SearchProblem ):\n",
        "    \n",
        "    # Let us specify the possible knight moves as a class attribute\n",
        "    moves = ((1,2), (2,1), (-1,2), (2,-1), \n",
        "             (1,-2), (-2,1), (-1,-2), (-2,-1))\n",
        "\n",
        "    def __init__(self, X, Y):\n",
        "        self.X = X\n",
        "        self.Y = Y\n",
        "        board = [ [0 for x in range(X)]\n",
        "                  for y in range(Y)]\n",
        "        self.initial_state = (0,None,board)\n",
        "        self.last_move = X*Y\n",
        "        \n",
        "    def possible_actions(self, state):\n",
        "        # For the initial move you can place on any square\n",
        "        if state[0]==0: # initial state\n",
        "            # Return list of all possible (x,y) pairs\n",
        "            return [(x,y) for x in range(self.X)\n",
        "                          for y in range(self.Y)]\n",
        "        \n",
        "        ## Otherwise check moves after the first move\n",
        "        x,y  = state[1] # position after previous move\n",
        "        actions = []\n",
        "        ## Condier all possible nights moves\n",
        "        for (mx, my) in KnightsTour.moves:\n",
        "            # Find coordinates of position after the move\n",
        "            nx, ny = (x+mx, y+my)\n",
        "            # Ignore cases where would move off the board\n",
        "            if nx<0 or ny<0 or nx >=self.X or ny>=self.Y:\n",
        "                continue\n",
        "            # Check whether has previously been at that space\n",
        "            board = state[2]\n",
        "            if board[ny][nx]==0: # 0 means has not been there.\n",
        "                actions.append((nx,ny))\n",
        "        return actions\n",
        "            \n",
        "    def successor(self, state, action):\n",
        "        move = state[0] + 1        \n",
        "        newboard = deepcopy(state[2])\n",
        "        x,y = action\n",
        "        newboard[y][x]=move\n",
        "        return (move, (x,y), newboard)\n",
        "    \n",
        "    def goal_test(self,state):\n",
        "        return state[0] == self.last_move\n",
        "    \n",
        "    def display_state(self,state):\n",
        "        board = state[2]\n",
        "        for row in board:\n",
        "            for square in row:\n",
        "                print( f\"{square:>2}\", end=\" \")\n",
        "            print()\n",
        "                \n",
        "        "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vA4cAMuPNEtC"
      },
      "source": [
        "### Creating a Knight's Tour Problem instance\n",
        "We can now create instances of the `KnightsTour` class corresponding to solving it on different board sizes.\n",
        "Let's try creating a 3x4 board, and we will then take a look at the `initial_state` for the problem we have created:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "cnCPIoVMNEtC"
      },
      "outputs": [],
      "source": [
        "kt = KnightsTour(3,4)\n",
        "kt.initial_state"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0dnuvxXzNEtE"
      },
      "source": [
        "Here we see that: no move has yet been taken, the knight does not have a current possition, and the inital board state has four rows of three squares, all set to `0` (meaning the square has not yet been visited).\n",
        "\n",
        "We can also use the `display_state` method to see the board in a more visually comprehensible form:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "0NI95aNiNEtF"
      },
      "outputs": [],
      "source": [
        "kt.display_state(kt.initial_state)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "isU54SRZNEtG"
      },
      "source": [
        "### Applying the Search Function\n",
        "We are now ready to apply the search function. Let us start with a test of the depth first (`'DF/FIFO'`) mode:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "C7JN-rfgNEtG"
      },
      "outputs": [],
      "source": [
        "search(kt, 'DF/FIFO', 10000)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "a2Ha9O70NEtJ"
      },
      "source": [
        "## Knights Tour Exercises\n",
        "\n",
        "Test and  compare  the  performance  of breadth first search (using argument 'breadth_first' for the 3rd parameter) and depth first search (use argument 'depth_first') on the Knight’s Tour puzzle for each of the board sizes 3x4, 4x4, 4x5 and 5x5.\n",
        "Construct a table, which clearly shows all significant information generated by each of the search tests (i.e. result of the search, nodes generated, time taken, length of path).\n",
        "\n",
        "Which of the strategies breadth first search and depth first search is best for solving the Knight’s Tour problem.\n",
        "Can you explain this? \n"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.8"
    },
    "colab": {
      "name": "SearchExercise4.ipynb",
      "provenance": []
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}